package main

import (
	"fmt"
)

// 自己实现的链表
/****************************************/
/**
head := NewListNode([]int{1, 2, 3})
printLinkedList(head)
*/

type ListNode struct {
	Val  int
	Next *ListNode
}

func NewListNode(nums []int) *ListNode {
	return createLinkedList(nums)
}

func createLinkedList(nums []int) *ListNode {

	if len(nums) == 0 { return nil }

	head := &ListNode{ Val: nums[0] }

	cur := head
	for i := 1; i < len(nums); i++ {
		cur.Next = &ListNode{ Val: nums[i] }
		cur = cur.Next
	}

	return head
}

func printLinkedList(head *ListNode) {

	cur := head
	for cur != nil {
		fmt.Print(cur.Val, "->")
		cur = cur.Next
	}
	fmt.Println("NULL")
}
/****************************************/

/**
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2.4 MB, 在所有 Go 提交中击败了100.00%的用户
 */
func partition(head *ListNode, x int) *ListNode {

	if head == nil || head.Next == nil { return head }

	dummy1, dummy2 := &ListNode{}, &ListNode{}
	tail1, tail2 := dummy1, dummy2

	for p := head; p != nil; p = p.Next {
		if p.Val < x {
			tail1.Next = p
			tail1 = tail1.Next
		} else {
			tail2.Next = p
			tail2 = tail2.Next
		}
	}

	tail2.Next = nil
	tail1.Next = dummy2.Next

	return dummy1.Next
}

func main() {

	head := NewListNode([]int{1, 4, 3, 2, 5, 2})
	printLinkedList(partition(head, 3))
}
